class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        right_index = n - 1
        left_index = 1
        while left_index != right_index:
            mid_index = (right_index + left_index) // 2
            left_value = 0
            for item in nums:
                if left_index <= item <= mid_index:
                    left_value += 1
            if left_value > mid_index - left_index + 1:
                right_index = mid_index
            else:
                left_index = mid_index + 1
        return right_index



data = Solution()
nums = [3,1,3,4,2]
print(data.findDuplicate(nums))